#include <iostream>

using namespace std;

// 125 验证回文串
// 给定已给字符串，只看其中的数字和字母，忽略大小写，判断这个字符串是否为回文串？
// 输入: s = "A man, a plan, a canal: Panama"
// 输出：true
// 解释："amanaplanacanalpanama" 是回文串。
// https://leetcode.cn/problems/valid-palindrome/description/

class Solution {
public:
    bool isPalindrome(string s) {
        int i = next_alpha_numeric(s, 0);
        int j = prev_alpha_numeric(s, s.size() - 1);
        while(i <= j) {
            if(tolower(s[i]) != tolower(s[j]))
                return false;
            i = next_alpha_numeric(s, i + 1);
            j = prev_alpha_numeric(s, j - 1);
        }
        return true;
    }

private:
    // 从index开始前往后找，找到第一个字母或数字的字符，返回索引。找不到则返回最后位置的下一个。
    int next_alpha_numeric(const string& s, int index) {
        for(int i = index; i < s.size(); i++)
            if(isalnum(s[i]))
                return i;
        return s.size();
    }
    // 从index开始后往前找，找到一个字母或数字的字符，返回索引。找不到则返回最后位置的下一个。
    int prev_alpha_numeric(const string& s, int index) {
        for(int i = index; i >= 0; i--)
            if(isalnum(s[i]))
                return i;
        return -1;
    }
};

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
